package com.vint.basic;

/**
 * Copyright (C) 2017, Xiaomi Inc. All rights reserved.
 * Created by vint @ 2017/10/29.
 * in leetcode
 */
public class BinarySearch {

	//int[] a是有序的，查找到则返回index,否则返回-1
	//两种方式，迭代或递归，这里迭代
	public static int rank(int[] a, int key){
		if(null==a||a.length<=0)return -1;
		int start = 0;
		int end = a.length-1;
		while (start<=end){
			int mid = start + (end - start)/2;
			if(key<a[mid]){
				end = mid -1;
			}else if(key>a[mid]) {
				start = mid + 1;
			}else {
				return mid;
			}
		}
		return -1;

	}
	public static void main(String[] args) {
		int[] a1 = {1,3,6,8,9,11};
		int[] a2 = {1,1};
		System.out.println(rank(a1,3));
		System.out.println(rank(a1,4));
		System.out.println(rank(a2,4));

	}
}
